package com.cuz.hot100;

public class Q52solveNQueens2 {
    public static void main(String[] args) {
//        System.out.println(solveNQueens1(1));
        System.out.println(solveNQueens2(4));
    }

    public static int solveNQueens2(int n) {
        int[] res = {0};
        for (int col = 0; col < n; col++) {
            int[] memory = new int[n];
            memory[0] = col;
            process(memory, n, 1, res);
        }
        return res[0];
    }

    /**
     * 回溯
     *
     * @param memory 第index行放在了memory[index]列
     * @param n      总共多少个皇后
     * @param curRow 当前第几行 从0开始
     * @param res    结果
     */
    private static void process(int[] memory, int n, int curRow, int[] res) {
        if (curRow == n) {
            res[0]++;
            return;
        }
        for (int colToSave = 0; colToSave < n; colToSave++) {
            if (isValid(curRow, colToSave, memory)) {
                memory[curRow] = colToSave;
                process(memory, n, curRow + 1, res);
                memory[curRow] = 0;
            }
        }
    }

    private static boolean isValid(int x, int y, int[] memory) {
        for (int row = 0; row < x; row++) {
            int col = memory[row];
            if (col == y) {
                return false;
            }
            if (Math.abs(row - x) == Math.abs(col - y)) {
                return false;
            }
        }
        return true;
    }
}
